{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 继续他们的石子游戏。几堆石子 <strong>排成一行</strong> ，每堆石子都对应一个得分，由数组 <code>stoneValue</code> 给出。</p>\n",
    "\n",
    "<p>Alice 和 Bob 轮流取石子，<strong>Alice</strong> 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 <strong>1、2 或 3 堆石子</strong> 。比赛一直持续到所有石头都被拿走。</p>\n",
    "\n",
    "<p>每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 <strong>0</strong> 。</p>\n",
    "\n",
    "<p>比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。</p>\n",
    "\n",
    "<p>假设 Alice 和 Bob 都采取 <strong>最优策略</strong> 。</p>\n",
    "\n",
    "<p>如果 Alice 赢了就返回 <code>\"Alice\"</code> <em>，</em>Bob 赢了就返回<em> </em><code>\"Bob\"</code><em>，</em>分数相同返回 <code>\"Tie\"</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,2,3,7]\n",
    "<strong>输出：</strong>\"Bob\"\n",
    "<strong>解释：</strong>Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,2,3,-9]\n",
    "<strong>输出：</strong>\"Alice\"\n",
    "<strong>解释：</strong>Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。\n",
    "如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。\n",
    "如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。\n",
    "注意，他们都应该采取 <strong>最优策略 </strong>，所以在这里 Alice 将选择能够使她获胜的方案。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,2,3,6]\n",
    "<strong>输出：</strong>\"Tie\"\n",
    "<strong>解释：</strong>Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stoneValue.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000&nbsp;&lt;= stoneValue[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-iii](https://leetcode.cn/problems/stone-game-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-iii](https://leetcode.cn/problems/stone-game-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,7]', '[1,2,3,-9]', '[1,2,3,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        opti = [None] * (n+1) # 存储当剩余位数为idx时最优能赢多少\n",
    "        opti[-1] = 0 # 最后选完了没得选（为了索引不报错）\n",
    "        for idx in range(n-1,-1,-1):\n",
    "            if idx == n-1:\n",
    "                opti[idx] = stoneValue[idx]\n",
    "            elif idx == n-2:\n",
    "                opti[idx] = max(stoneValue[idx] - opti[idx+1], sum(stoneValue[idx:]))\n",
    "            else:\n",
    "                opti[idx] = stoneValue[idx] - opti[idx+1]\n",
    "                opti[idx] = max(opti[idx],sum(stoneValue[idx:idx+2])-opti[idx+2])\n",
    "                opti[idx] = max(opti[idx],sum(stoneValue[idx:idx+3])-opti[idx+3])\n",
    "        if opti[0] > 0:\n",
    "            return \"Alice\" \n",
    "        elif opti[0] < 0:\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            return \"Tie\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, a: List[int]) -> str:\n",
    "        \"\"\"\n",
    "        dp[i][player] 表示输入为 stoneValue[i:] 的时候，当前玩家为 player 的时候\n",
    "                         Alice 能够拿到的最大得分\n",
    "        dp[i][alice] = max(\n",
    "            a[i] + dp[i + 1][bob],\n",
    "            a[i] + a[i + 1] + dp[i + 2][bob],\n",
    "            a[i] + a[i + 1] + a[i + 2] + dp[i + 3][bob],\n",
    "        )\n",
    "        dp[i][bob] = min(\n",
    "            dp[i + 1][alice],\n",
    "            dp[i + 2][alice],\n",
    "            dp[i + 3][alice],\n",
    "        )\n",
    "        base case:\n",
    "            dp[n - 1][alice] = a[-1]\n",
    "            dp[n - 1][bob] = 0\n",
    "        \"\"\"\n",
    "        n = len(a)\n",
    "        dp = [[-float(\"inf\"), float(\"inf\")] for i in range(n)]\n",
    "        alice, bob = 0, 1\n",
    "        dp[-1][alice] = a[-1]\n",
    "        dp[-1][bob] = 0\n",
    "        for i in reversed(range(n - 1)):\n",
    "            dp[i][alice] = max(\n",
    "                a[i] + dp[i + 1][bob],\n",
    "                a[i] + a[i + 1] + (dp[i + 2][bob] if i + 2 < n else 0),\n",
    "                a[i] + a[i + 1] + (a[i + 2] if i + 2 < n else 0) + (dp[i + 3][bob] if i + 3 < n else 0),\n",
    "            )\n",
    "            dp[i][bob] = min(\n",
    "                dp[i + 1][alice],\n",
    "                (dp[i + 2][alice] if i + 2 < n else 0),\n",
    "                (dp[i + 3][alice] if i + 3 < n else 0),\n",
    "            )\n",
    "        print(dp)\n",
    "        alice = dp[0][alice]\n",
    "        bob = sum(a) - alice\n",
    "        if alice > bob:\n",
    "            return \"Alice\"\n",
    "        elif alice == bob:\n",
    "            return \"Tie\"\n",
    "        else:\n",
    "            return \"Bob\"\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        import numpy as np\n",
    "        f = [0 for _ in range(len(stoneValue) + 1)]\n",
    "        _sum = [0 for _ in range(len(stoneValue) + 1)]\n",
    "        for i in [len(stoneValue) - x - 1 for x in range(len(stoneValue))]:\n",
    "            _sum[i] = _sum[i + 1] + stoneValue[i]\n",
    "#             print (_sum[i + 1], sum(stoneValue[i+1:]))\n",
    "            f[i] = stoneValue[i] + _sum[i + 1] - f[i+1]\n",
    "            for j in range(2, 4):\n",
    "                if i + j >= len(stoneValue) + 1:\n",
    "                    break\n",
    "                f[i] = max(f[i], sum(stoneValue[i:i+j]) + _sum[i+j] - f[i+j])\n",
    "#         print (f[0], sum(stoneValue) - f[0])\n",
    "        if f[0] * 2 > sum(stoneValue):\n",
    "            return 'Alice'\n",
    "        if f[0] * 2 == sum(stoneValue):\n",
    "            return 'Tie'\n",
    "        return 'Bob'\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        dp = [[[0, 0, 0], [0, 0, 0]] for i in range(len(stoneValue)+3)]\n",
    "        s = 0\n",
    "        for i in range(len(stoneValue)-1, -1, -1):\n",
    "            s += stoneValue[i]\n",
    "            dp[i][0][0] = s - max(dp[i+1][1])\n",
    "            dp[i][0][1] = s - max(dp[i+2][1])\n",
    "            dp[i][0][2] = s - max(dp[i+3][1])\n",
    "            dp[i][1][0] = s - max(dp[i+1][0])\n",
    "            dp[i][1][1] = s - max(dp[i+2][0])\n",
    "            dp[i][1][2] = s - max(dp[i+3][0])\n",
    "        for i in (0, 1, 2):\n",
    "            if dp[0][0][i] * 2 > s:\n",
    "                return \"Alice\"\n",
    "        if dp[0][0][0] * 2 == s or dp[0][0][1] * 2 == s or dp[0][0][2] * 2 == s:\n",
    "            return \"Tie\"\n",
    "        return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.cache = None\n",
    "        self.stoneValue = None\n",
    "\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        self.cache = {}\n",
    "        self.stoneValue = stoneValue\n",
    "        ans = self._search(pos=0)\n",
    "        if ans > 0:\n",
    "            return 'Alice'\n",
    "        elif ans < 0:\n",
    "            return 'Bob'\n",
    "\n",
    "        return 'Tie'\n",
    "\n",
    "    def _search(self, pos: int) -> None:\n",
    "        if pos in self.cache:\n",
    "            return self.cache[pos]\n",
    "\n",
    "        left = len(self.stoneValue) - pos\n",
    "        if left == 1:\n",
    "            take_one = self.stoneValue[pos]\n",
    "            self.cache[pos] = take_one\n",
    "        elif left == 2:\n",
    "            take_two = self.stoneValue[pos] + self.stoneValue[pos+1]\n",
    "            take_one = self.stoneValue[pos] - self._search(pos=pos+1)\n",
    "            self.cache[pos] = max(take_two, take_one)\n",
    "        elif left == 3:\n",
    "            take_three = self.stoneValue[pos] + self.stoneValue[pos+1] + self.stoneValue[pos+2]\n",
    "            take_two = self.stoneValue[pos] + self.stoneValue[pos+1] - self._search(pos=pos+2)\n",
    "            take_one = self.stoneValue[pos] - self._search(pos=pos+1)\n",
    "            self.cache[pos] = max(take_three, take_two, take_one)\n",
    "        elif left > 3:\n",
    "            take_three = self.stoneValue[pos] + self.stoneValue[pos+1] + self.stoneValue[pos+2] - self._search(pos=pos+3)\n",
    "            take_two = self.stoneValue[pos] + self.stoneValue[pos+1] - self._search(pos=pos+2)\n",
    "            take_one = self.stoneValue[pos] - self._search(pos=pos+1)\n",
    "            self.cache[pos] = max(take_three, take_two, take_one)\n",
    "        \n",
    "        return self.cache[pos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        self.stoneValue = stoneValue\n",
    "        self.dp = [1001] * len(stoneValue)\n",
    "        score = self.helper(0)\n",
    "        # print(self.dp)\n",
    "        # print(score)\n",
    "        if score == 0:\n",
    "            return 'Tie'\n",
    "        elif score > 0:\n",
    "            return 'Alice' \n",
    "        else:\n",
    "            return 'Bob'\n",
    "    \n",
    "    def helper(self, i):\n",
    "        if self.dp[i] <= 1000:\n",
    "            pass\n",
    "        elif i == len(self.dp)-1:\n",
    "            self.dp[i] = self.stoneValue[i]\n",
    "        elif i == len(self.dp)-2:\n",
    "            self.dp[i] =  max(sum(self.stoneValue[-2:]), self.stoneValue[-2]-self.helper(i+1))\n",
    "        elif i == len(self.dp)-3:\n",
    "            self.dp[i] = max(sum(self.stoneValue[-3:]), sum(self.stoneValue[-3:-1])-self.helper(i+2),self.stoneValue[-3]-self.helper(i+1))\n",
    "        else:\n",
    "            self.dp[i] = max(self.stoneValue[i] - self.helper(i+1), sum(self.stoneValue[i:i+2]) - self.helper(i+2), sum(self.stoneValue[i:i+3]) - self.helper(i+3))\n",
    "        return self.dp[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, stoneValue, presum, i, n):\n",
    "        if i == n - 1:\n",
    "            return stoneValue[n - 1]\n",
    "        if i > n - 1:\n",
    "            return 0\n",
    "        if i in self.vis:\n",
    "            return self.vis[i]\n",
    "\n",
    "        total = presum[n - 1]\n",
    "        if i > 0:\n",
    "            total -= presum[i - 1]\n",
    "\n",
    "        ans = -1e10\n",
    "        for j in range(1, 4):\n",
    "            cnt_ans = total - self.dfs(stoneValue, presum, i + j, n)\n",
    "            ans = max(ans, cnt_ans)\n",
    "        self.vis[i] = ans\n",
    "        return ans\n",
    "\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        self.vis = {}\n",
    "        presum = [stoneValue[0]]\n",
    "        n = len(stoneValue)\n",
    "        for i in range(1, n):\n",
    "            presum.append(presum[-1] + stoneValue[i])\n",
    "\n",
    "        ans = self.dfs(stoneValue, presum, 0, n)\n",
    "        diff = 2 * ans - sum(stoneValue)  # Alice - Bob\n",
    "        if diff > 0:\n",
    "            return 'Alice'\n",
    "        if diff < 0:\n",
    "            return 'Bob'\n",
    "        return 'Tie'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        preSum = list(accumulate(stoneValue, initial=0))\n",
    "        dp = [-inf for _ in range(n + 1)]\n",
    "        dp[n] = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for c in range(1, 4):\n",
    "                if i + c <= n:\n",
    "                    dp[i] = max(dp[i], preSum[-1] - preSum[i] - dp[i + c])\n",
    "        \n",
    "        # 从 i 开始\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            val = -inf\n",
    "            # 模拟选择 3 堆，取最大得分\n",
    "            for c in range(1, 4):\n",
    "                if i + c <= n:\n",
    "                    val = max(val, preSum[-1] - preSum[i] - dfs(i + c))\n",
    "            return val\n",
    "        a = dp[0]\n",
    "        b = preSum[-1] - a\n",
    "        #print(a, b)\n",
    "        return 'Alice' if a > b else 'Bob' if a < b else 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, stoneValue, memo, idx):\n",
    "        if idx == len(stoneValue): return 0\n",
    "        if memo[idx] != None: return memo[idx]\n",
    "\n",
    "        ans = -float('inf')\n",
    "        cur = idx\n",
    "        score = 0\n",
    "        while cur < idx + 3 and cur < len(stoneValue):\n",
    "            score += stoneValue[cur]\n",
    "            ans = max(ans, score - self.dfs(stoneValue, memo, cur + 1))\n",
    "            cur += 1\n",
    "        \n",
    "        memo[idx] = ans\n",
    "        return ans\n",
    "\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        memo = [None] * n\n",
    "        score = self.dfs(stoneValue, memo, 0)\n",
    "        if score > 0:\n",
    "            return \"Alice\"\n",
    "        elif score < 0:\n",
    "            return \"Bob\"\n",
    "        else:\n",
    "            return \"Tie\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "\n",
    "        n = len(stoneValue)\n",
    "        s = [0 for _ in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            s[i] = s[i+1] + stoneValue[i]\n",
    "\n",
    "        mx = [0 for _ in range(n+1)]\n",
    "        def dfs(idx):\n",
    "            if idx == n: return 0 \n",
    "            \n",
    "            opposite = []\n",
    "            for i in range(1,4):\n",
    "                if idx+i <= n:\n",
    "                    if mx[idx+i] == 0:\n",
    "                        mx[idx+i] = dfs(idx+i)\n",
    "                    opposite.append(mx[idx+i])\n",
    "\n",
    "            res = s[idx] - min(opposite)\n",
    "            mx[idx] = res\n",
    "            return res\n",
    "\n",
    "        a = dfs(0)\n",
    "        b = s[0] - a\n",
    "\n",
    "        ''' '''\n",
    "        if a>b: return \"Alice\"\n",
    "        elif a==b: return \"Tie\"\n",
    "        else: return \"Bob\" \n",
    "        \n",
    "        # return mx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        score = [None] * len(stoneValue)\n",
    "        start = 0\n",
    "        \n",
    "        def game(stonevalues, start):\n",
    "            values = stonevalues\n",
    "            if(start >= len(values)):\n",
    "                return 0\n",
    "            if(score[start] != None): return score[start]\n",
    "            if(start <= len(values) - 1):\n",
    "                v = values[start] - game(values, start+1)\n",
    "            if(start + 1 <= len(values) - 1):\n",
    "                v = max(v, values[start] + values[start+1] - game(values, start+2))\n",
    "            if(start + 2 <= len(values) - 1):\n",
    "                v = max(v, values[start] + values[start+1] + values[start+2] - game(values, start+3))\n",
    "            score[start] = v\n",
    "            return v\n",
    "            \n",
    "        res = game(stoneValue, 0)\n",
    "        if(res > 0): return \"Alice\"\n",
    "        elif(res < 0): return \"Bob\"\n",
    "        else: return \"Tie\"\n",
    "\n",
    "        '''\n",
    "        n =len(stoneValue)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >=n:\n",
    "                return 0\n",
    "            ans =-1\n",
    "            if i+1<=n:\n",
    "                ans = max(ans,stoneValue[i]-dfs(i+1))\n",
    "            if i+2<=n:\n",
    "                ans = max(ans,stoneValue[i]+stoneValue[i+1]-dfs(i+2))\n",
    "            if i+3<=n:\n",
    "                ans = max(ans,stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]-dfs(i+3))\n",
    "            return ans \n",
    "        \n",
    "        t = dfs(0)\n",
    "        if t>0:return 'Alice'\n",
    "        elif t<0:return 'Bob'\n",
    "        else:return 'Tie'\n",
    "        '''\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        @cache\n",
    "        def back(l):\n",
    "            if l == n:return 0\n",
    "            res = -inf\n",
    "            lin = 0\n",
    "            for i in range(1,min(4,n-l+1)):\n",
    "                lin += stoneValue[l+i-1]\n",
    "                res = max(res,lin-back(l+i))\n",
    "            return res\n",
    "        res = back(0)\n",
    "        del back\n",
    "        if res > 0:\n",
    "            return \"Alice\"\n",
    "        elif res == 0:\n",
    "            return \"Tie\"\n",
    "        else:\n",
    "            return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        acc = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                return [0, 0]\n",
    "            if i == n - 1:\n",
    "                return [stoneValue[-1], 0]\n",
    "            choice = min(n - i, 3)\n",
    "            res = -inf\n",
    "            for j in range(1, choice + 1):\n",
    "                fir, sec = f(i + j)\n",
    "                res = max(res, sum(stoneValue[i: i + j]) + sec)\n",
    "            return [res, acc[n] - acc[i] - res]\n",
    "        a, b = f(0)\n",
    "        if a > b: return \"Alice\"\n",
    "        elif a < b: return \"Bob\"\n",
    "        return \"Tie\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        memo=defaultdict(int)\n",
    "        n=len(stoneValue)\n",
    "\n",
    "        def dp(i,memo):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if memo[i]:\n",
    "                return memo[i]\n",
    "            memo[i]=-inf\n",
    "            for j in range(1,4):\n",
    "                \n",
    "                memo[i]=max(memo[i],sum(stoneValue[i:i+j])-dp(i+j,memo))\n",
    "               \n",
    "\n",
    "            return memo[i]\n",
    "\n",
    "        ans=dp(0,memo)\n",
    "\n",
    "        if ans>0:\n",
    "            return \"Alice\"\n",
    "        elif ans==0:\n",
    "            return \"Tie\"\n",
    "        return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        all_sum = sum(stoneValue)\n",
    "        n = len(stoneValue)\n",
    "        @lru_cache\n",
    "        def dfs(cur):\n",
    "            if cur>=n:return 0 #<0输，=0平,>0胜\n",
    "            res = -dfs(cur+1)+sum(stoneValue[cur:cur+1])\n",
    "            for i in range(2,4):\n",
    "                res = max(res,-dfs(cur+i)+sum(stoneValue[cur:cur+i]))\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        if ans==0:return 'Tie'\n",
    "        elif ans>0:return 'Alice'\n",
    "        else:return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "\n",
    "        # 返回从i开始到结束Alice的得分和Bob的得分\n",
    "        @lru_cache(None)\n",
    "        def f(i, people):\n",
    "            if i == n:\n",
    "                return [0, 0]\n",
    "            if i == n - 1:\n",
    "                tmp = f(i + 1, people * -1)\n",
    "                if people == 1:\n",
    "                    return [stoneValue[i] + tmp[0], tmp[1]]\n",
    "                return [tmp[0], tmp[1] + stoneValue[i]]\n",
    "            elif i == n - 2:\n",
    "                tmp1 = f(i + 1, people * -1)\n",
    "                tmp2 = f(i + 2, people * -1)\n",
    "                if people == 1:\n",
    "                    if stoneValue[i] + tmp1[0] - tmp1[1] > stoneValue[i] + stoneValue[i + 1] + tmp2[0] - tmp2[1]:\n",
    "                        return [stoneValue[i] + tmp1[0], tmp1[1]]\n",
    "                    else:\n",
    "                        return [stoneValue[i] + stoneValue[i + 1] + tmp2[0], tmp2[1]]\n",
    "                else:\n",
    "                    if stoneValue[i] + tmp1[1] - tmp1[0] > stoneValue[i] + stoneValue[i + 1] + tmp2[1] - tmp2[0]:\n",
    "                        return [tmp1[0], stoneValue[i] + tmp1[1]]\n",
    "                    else:\n",
    "                        return [tmp2[0], stoneValue[i] + stoneValue[i + 1] + tmp2[1]]\n",
    "            else:\n",
    "                tmp1 = f(i + 1, people * -1)\n",
    "                tmp2 = f(i + 2, people * -1)\n",
    "                tmp3 = f(i + 3, people * -1)\n",
    "                if people == 1:\n",
    "                    t1 = stoneValue[i] + tmp1[0] - tmp1[1]\n",
    "                    t2 = stoneValue[i] + stoneValue[i + 1] + tmp2[0] - tmp2[1]\n",
    "                    t3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + tmp3[0] - tmp3[1]\n",
    "                    if t3 == max(t1, t2, t3):\n",
    "                        return [stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + tmp3[0], tmp3[1]]\n",
    "                    elif t2 == max(t1, t2, t3):\n",
    "                        return [stoneValue[i] + stoneValue[i + 1] + tmp2[0], tmp2[1]]\n",
    "                    else:\n",
    "                        return [stoneValue[i] + tmp1[0], tmp1[1]]\n",
    "                else:\n",
    "                    t1 = stoneValue[i] + tmp1[1] - tmp1[0]\n",
    "                    t2 = stoneValue[i] + stoneValue[i + 1] + tmp2[1] - tmp2[0]\n",
    "                    t3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + tmp3[1] - tmp3[0]\n",
    "                    if t3 == max(t1, t2, t3):\n",
    "                        return [tmp3[0], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + tmp3[1]]\n",
    "                    elif t2 == max(t1, t2, t3):\n",
    "                        return [tmp2[0], stoneValue[i] + stoneValue[i + 1] + tmp2[1]]\n",
    "                    else:\n",
    "                        return [tmp1[0], stoneValue[i] + tmp1[1]]\n",
    "\n",
    "        ans = f(0, 1)\n",
    "        if ans[0] > ans[1]:\n",
    "            return \"Alice\"\n",
    "        elif ans[0] == ans[1]:\n",
    "            return \"Tie\"\n",
    "        return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, values: List[int]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, p):\n",
    "            if i == len(values):\n",
    "                return 0, 0\n",
    "            s = 0\n",
    "            mx = -inf\n",
    "            mxt = None\n",
    "            for l in range(i, min(len(values), i + 3)):\n",
    "                s += values[l]\n",
    "                t = dp(l + 1, 1 - p)\n",
    "                t = list(t)\n",
    "                t[p] += s\n",
    "                if t[p] > mx:\n",
    "                    mx = t[p]\n",
    "                    mxt = t\n",
    "                elif t[p] == mx and t[1 - p] < mxt[1 - p]:\n",
    "                    mxt = t\n",
    "\n",
    "            return tuple(mxt)\n",
    "\n",
    "        dpa = dp(0, 0)\n",
    "\n",
    "        dp.cache_clear()\n",
    "        \n",
    "        if dpa[0] == dpa[1]:\n",
    "            return 'Tie'\n",
    "        elif dpa[0] > dpa[1]:\n",
    "            return 'Alice'\n",
    "        else:\n",
    "            return 'Bob'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        s = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "        @lru_cache\n",
    "        def dfs(idx):\n",
    "            # if n - idx <= 3:\n",
    "            #     return min([s[n] - s[idx] for ])\n",
    "            if idx >= n: return 0\n",
    "            return s[n] - s[idx] - min(dfs(idx+1), dfs(idx+2), dfs(idx+3))\n",
    "        res = dfs(0)\n",
    "        if res > s[-1] - res: return \"Alice\"\n",
    "        elif res == s[-1] - res: return \"Tie\"\n",
    "        else: return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        pres = list(accumulate(stoneValue, initial=0))\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0 \n",
    "            res = max(pres[min(i + 1, n)] - pres[i] - dfs(i + 1), pres[min(i + 2, n)] - pres[i] - dfs(i + 2), pres[min(i + 3, n)] - pres[i] - dfs(i + 3))\n",
    "            return res\n",
    "        res = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return 'Alice' if res > 0 else 'Bob' if res < 0 else 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, piles: List[int]) -> str:\n",
    "        n = len(piles)\n",
    "        dp = [0]*(n+1) #从当前位置到最后数组和\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i] = dp[i+1]+piles[i]\n",
    "        @lru_cache(None)\n",
    "        def dfs(left): #当从第 left 堆石子开始拿，允许拿 M <= x <= 2 * M 时，在剩余石子中所能拿到的最大值\n",
    "            if left>n:\n",
    "                return 0\n",
    "            ans = float('-inf')\n",
    "            for x in range(1,4):\n",
    "                ans = max(ans,dp[left]-dfs(left+x) )\n",
    "            return ans\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        if ans*2>dp[0]:return 'Alice'\n",
    "        elif ans*2<dp[0]:return 'Bob'\n",
    "        return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        suffix = stoneValue\n",
    "        for i in range(len(stoneValue)-2, -1, -1):\n",
    "            suffix[i] += suffix[i+1]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= len(stoneValue):\n",
    "                return 0\n",
    "            return suffix[i] - min(dfs(i + x) for x in range(1,4))\n",
    "             \n",
    "        if 2 * dfs(0) == suffix[0]: return 'Tie'\n",
    "        return 'Bob' if 2 * dfs(0) < suffix[0] else 'Alice'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, nums: List[int]) -> str:\n",
    "        n=len(nums)\n",
    "        su=sum(nums)\n",
    "        s=[0]*n\n",
    "        s[-1]=nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            s[i]=s[i+1]+nums[i]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            return s[i]-min(dfs(i+k) for k in range(1,4))\n",
    "        if su-dfs(0)>dfs(0):\n",
    "            return 'Bob'\n",
    "        elif su-dfs(0)<dfs(0):\n",
    "            return 'Alice'\n",
    "        else :\n",
    "            return 'Tie'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        sm = list(accumulate(stoneValue, initial=0))\n",
    "        \n",
    "        @cache\n",
    "        def first(i: int, j: int) -> int:\n",
    "            # if j - i + 1 <= 3:\n",
    "            #     return sum(stoneValue[i:j+1])\n",
    "            # 先手必须选择一个石头\n",
    "            # 越界没得选\n",
    "            if i > j:\n",
    "                return 0\n",
    "            res = stoneValue[i] + second(i + 1, j)\n",
    "            for k in range(3):\n",
    "                if k + i > j: break\n",
    "                res = max(res, second(i + k + 1, j) + sm[i + k + 1] - sm[i])\n",
    "            return res\n",
    "        \n",
    "        @cache\n",
    "        def second(i: int, j: int) -> int:\n",
    "            # 越界你后手代表没得选\n",
    "            res = inf if j >= i else 0\n",
    "            for k in range(3):\n",
    "                if k + i > j: break\n",
    "                res = min(first(i + k + 1, j), res)\n",
    "            return res\n",
    "        s1, s2 = first(0, n - 1), second(0, n - 1)\n",
    "        first.cache_clear()\n",
    "        second.cache_clear()\n",
    "        if s1 > s2:\n",
    "            return 'Alice'\n",
    "        elif s1 < s2:\n",
    "            return 'Bob'\n",
    "        return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        @cache\n",
    "        def dp(i: int) -> int:\n",
    "            return max((sum(stoneValue[i:j + 1]) - dp(j + 1) for j in range(i, min(i + 3, len(stoneValue)))), default=0)\n",
    "\n",
    "        score = dp(0)\n",
    "        return \"Alice\" if score > 0 else \"Bob\" if score < 0 else \"Tie\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str: \n",
    "        n = len(stoneValue)\n",
    "        f = [inf] * n\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1] + stoneValue[i - 1]\n",
    "        def dfs(x):\n",
    "            if f[x] != inf: return f[x]\n",
    "            if x == n - 1:\n",
    "                f[x] = stoneValue[-1]\n",
    "            elif x == n - 2:\n",
    "                f[x] = max(stoneValue[-2], stoneValue[-2] + stoneValue[-1])\n",
    "            elif x == n - 3:\n",
    "                f[x] = max(stoneValue[-3] + stoneValue[-2] + stoneValue[-1] - dfs(x + 1), stoneValue[-3] + stoneValue[-2], stoneValue[-3] + stoneValue[-2] + stoneValue[-1])\n",
    "            else:\n",
    "                f[x] = s[n] - s[x] - min(dfs(x + 1), dfs(x + 2), dfs(x + 3))\n",
    "            return f[x]\n",
    "        ans = dfs(0)\n",
    "        if ans > s[n] / 2: return 'Alice'\n",
    "        if ans == s[n] / 2: return 'Tie'\n",
    "        if ans < s[n] / 2: return 'Bob'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        piles = stoneValue\n",
    "        n = len(piles)\n",
    "        \n",
    "        # Calculate prefix sums\n",
    "        prefix_sum = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            prefix_sum[i] = prefix_sum[i + 1] + piles[i]\n",
    "\n",
    "        # DP array to store results\n",
    "        dp = [float('-inf')] * (n+1)\n",
    "\n",
    "        def dfs(index):\n",
    "            if index >= n:\n",
    "                return 0\n",
    "            if dp[index] != float('-inf'):\n",
    "                return dp[index]\n",
    "\n",
    "            total = 0\n",
    "            for i in range(1, 4):\n",
    "                if index + i - 1 < n:\n",
    "                    total += piles[index + i - 1]\n",
    "                    dp[index] = max(dp[index], total + prefix_sum[index+i] - dfs(index + i))\n",
    "\n",
    "            return dp[index]\n",
    "\n",
    "        temp = dfs(0)\n",
    "        if temp > prefix_sum[0] / 2:\n",
    "            return 'Alice'\n",
    "        elif temp < prefix_sum[0] / 2:\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        dic = {}\n",
    "        dic[n - 1] = stoneValue[-1]\n",
    "        dic[n]=0\n",
    "\n",
    "        def dp(m):\n",
    "            if m in dic: return dic[m]\n",
    "            res = 0\n",
    "            if m + 1 <= n:\n",
    "                res = stoneValue[m] - dp(m + 1)\n",
    "            if m + 2 <= n:\n",
    "                res = max(res, stoneValue[m] + stoneValue[m + 1] - dp(m + 2))\n",
    "            if m + 3 <= n:\n",
    "                res = max(res, stoneValue[m] + stoneValue[m + 1] + stoneValue[m + 2] - dp(m + 3))\n",
    "            dic[m] = res\n",
    "            return res\n",
    "\n",
    "        dp(0)\n",
    "        if dic[0] > 0:\n",
    "            return \"Alice\"\n",
    "        elif dic[0] < 0:\n",
    "            return \"Bob\"\n",
    "        return \"Tie\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        memo = {}\n",
    "        def minimax(index):\n",
    "            if index == len(stoneValue):\n",
    "                return 0\n",
    "            if index in memo:\n",
    "                return memo[index]\n",
    "            res = -float(\"inf\")\n",
    "            score = 0\n",
    "            for i in range(index, index+3):\n",
    "                if i < len(stoneValue):\n",
    "                    score += stoneValue[i]\n",
    "                    res = max(res, score - minimax(i+1))\n",
    "            memo[index] = res\n",
    "            return memo[index]\n",
    "\n",
    "        score = minimax(0)\n",
    "        if score == 0:\n",
    "            return \"Tie\"\n",
    "        elif score > 0:\n",
    "            return \"Alice\"\n",
    "        else:\n",
    "            return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        dp = {}\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i >= len(stoneValue):\n",
    "                return 0\n",
    "            if i in dp:\n",
    "                return dp[i]\n",
    "            res = float('-inf')\n",
    "            for j in range(i, min(i + 3, len(stoneValue))):\n",
    "                res = max(res, sum(stoneValue[i:j+1]) - dfs(j + 1))\n",
    "            \n",
    "            dp[i] = res\n",
    "            return dp[i]\n",
    "        alice = dfs(0)\n",
    "        if alice > 0: return 'Alice'\n",
    "        elif alice < 0: return 'Bob'\n",
    "        else: return 'Tie'\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i >= len(stoneValue): return 0\n",
    "            a1 = stoneValue[i] - dp(i+1)\n",
    "            a2 = stoneValue[i]+stoneValue[i+1] - dp(i+2) if i+1<len(stoneValue) else -inf\n",
    "            a3 = stoneValue[i]+stoneValue[i+1]+stoneValue[i+2] - dp(i+3)if i+2<len(stoneValue) else -inf\n",
    "            return max(a1,a2,a3)\n",
    "        x = dp(0)\n",
    "        if x > 0: return 'Alice'\n",
    "        if x < 0: return 'Bob'\n",
    "        return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: list[int]) -> str:\n",
    "        if not stoneValue:\n",
    "            return 'Tie'\n",
    "        n = len(stoneValue)\n",
    "\n",
    "        @cache\n",
    "        def func1(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            D_value = stoneValue[i] - func1(i + 1)\n",
    "            if i + 1 < n:\n",
    "                D_value = max(D_value, sum(stoneValue[i:i + 2]) - func1(i + 2))\n",
    "            if i + 2 < n:\n",
    "                D_value = max(D_value, sum(stoneValue[i:i + 3]) - func1(i + 3))\n",
    "            return D_value\n",
    "\n",
    "        D_value = func1(0)\n",
    "        if D_value > 0:\n",
    "            return 'Alice'\n",
    "        if D_value == 0:\n",
    "            return 'Tie'\n",
    "        return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        @cache # 从indx开始能赚多少分\n",
    "        def f(indx):\n",
    "            if indx == n:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for i in range(1, min(4,n-indx+1)):\n",
    "                res = max(res, sum(stoneValue[indx:indx+i]) - f(indx+i) )\n",
    "            return res\n",
    "        return 'Alice' if f(0)>0 else 'Bob' if f(0)<0 else 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        # 先手函数\n",
    "        @lru_cache(None)\n",
    "        def f(i: int):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if i == n - 1:\n",
    "                return stoneValue[i]\n",
    "            ans = stoneValue[i] + s(i + 1)\n",
    "            if i + 1 < n:\n",
    "                ans = max(ans, stoneValue[i] + stoneValue[i + 1] + s(i + 2))\n",
    "            if i + 2 < n:\n",
    "                ans = max(ans, stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + s(i + 3))\n",
    "            return ans\n",
    "        # 后手函数\n",
    "        @lru_cache(None)\n",
    "        def s(i: int):\n",
    "            if i >= n - 1:\n",
    "                return 0\n",
    "            return min(f(i + 1), f(i + 2), f(i + 3))\n",
    "        \n",
    "        scoreA = f(0)\n",
    "        f.cache_clear()\n",
    "        tot = sum(stoneValue)\n",
    "        scoreB = tot - scoreA\n",
    "        return \"Alice\" if scoreA > scoreB else \"Bob\" if scoreA < scoreB else \"Tie\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        h = list(accumulate(stoneValue)) + [0]\n",
    "        @cache\n",
    "        def p(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = h[i]-h[i-1]-p(i+1)\n",
    "            if i+2 <= n:\n",
    "                res = max(res, h[i+1]-h[i-1]-p(i+2))\n",
    "            if i+3 <= n:\n",
    "                res = max(res, h[i+2]-h[i-1]-p(i+3))\n",
    "            return res\n",
    "        res = p(0)\n",
    "        if res > 0:\n",
    "            return \"Alice\"\n",
    "        elif res < 0:\n",
    "            return \"Bob\"\n",
    "        else:\n",
    "            return \"Tie\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        pres = list(accumulate(stoneValue, initial=0))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0 \n",
    "            res = max(pres[min(i + 1, n)] - pres[i] - dfs(i + 1), pres[min(i + 2, n)] - pres[i] - dfs(i + 2), pres[min(i + 3, n)] - pres[i] - dfs(i + 3))\n",
    "            return res\n",
    "        res = dfs(0)\n",
    "        return 'Alice' if res > 0 else 'Bob' if res < 0 else 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        # 表示从i到n先手对后手的最大净胜分，结果为dfs(0,n),转移为选择第i,i+1，i+2\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==n:return 0\n",
    "            res=-inf\n",
    "            for j in range(i,min(i+3,n)):\n",
    "                res=max(res,presum[j+1]-presum[i]-dfs(j+1))\n",
    "            return res \n",
    "        n=len(stoneValue)\n",
    "        presum=list(itertools.accumulate(stoneValue,initial=0))\n",
    "        ans=dfs(0)\n",
    "        if ans>0:\n",
    "            return 'Alice'\n",
    "        elif ans<0:\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n, memo = len(stoneValue), {}\n",
    "        s = [0]*(n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            s[i] = s[i+1]+stoneValue[i]\n",
    "\n",
    "        def dfs(start):\n",
    "            if start >= n:\n",
    "                return 0\n",
    "            if start in memo:\n",
    "                return memo[start]\n",
    "            res = -float('inf')\n",
    "            for x in range(1, 4):\n",
    "                if start+x > n:\n",
    "                    break\n",
    "                res = max(res, s[start] - dfs(start+x))\n",
    "            memo[start] =res\n",
    "            return res\n",
    "        \n",
    "        Alice = dfs(0)\n",
    "        Bob = s[0] -dfs(0)\n",
    "        #print(Alice, Bob)\n",
    "\n",
    "        if Alice > Bob:\n",
    "            return \"Alice\"\n",
    "        elif Alice < Bob:\n",
    "            return \"Bob\"\n",
    "        else:\n",
    "            return \"Tie\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        self.stoneValue = stoneValue\n",
    "        res = self.dfs(0)\n",
    "        if res > 0:\n",
    "            return 'Alice'\n",
    "        elif res < 0:\n",
    "            return 'Bob'\n",
    "        return 'Tie'\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def dfs(self, index):\n",
    "        if index >= len(self.stoneValue):\n",
    "            return 0\n",
    "        if index == len(self.stoneValue)-1:\n",
    "            return self.stoneValue[-1]\n",
    "        max_val = float('-inf')\n",
    "        for i in range(1, 4):\n",
    "            max_val = max(max_val, sum(self.stoneValue[index:index+i]) - self.dfs(index+i))\n",
    "        return max_val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        \"\"\" DFS-memo \n",
    "        1. dfs(i) ==> current rewards \n",
    "        2. get the prefix Sum of stoneValue preSum \n",
    "        3. \n",
    "        rest_rewards = preSum[-1] - preSum[i]\n",
    "        if state == 1:\n",
    "            ans = rest_rewards - dfs(i+1)\n",
    "        if state == 2 ==> i + 1 < len(stoneValue):\n",
    "            ans = max(ans, rest_rewards - dfs(i+2))\n",
    "        if state = 3 ==> i + 2 < len(stoneValue):\n",
    "            ans = max(ans, rest_rewards - dfs(i+3))\n",
    "        4. termination: if i >= len(stoneValue): return 0 \n",
    "        5. start: dfs(0)\n",
    "        \"\"\"\n",
    "\n",
    "        preSum = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "        # print(preSum)\n",
    "        summ = sum(stoneValue)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0 \n",
    "\n",
    "            rest_rewards = preSum[-1] - preSum[i]\n",
    "            ans = rest_rewards - dfs(i+1)\n",
    "            if i + 1 < n:\n",
    "                ans = max(ans, rest_rewards - dfs(i+2))\n",
    "            if i + 2 < n:\n",
    "                ans = max(ans, rest_rewards - dfs(i+3))\n",
    "\n",
    "            return ans \n",
    "\n",
    "        ans = dfs(0)\n",
    "        if 2*ans > summ:\n",
    "            return \"Alice\"\n",
    "        elif 2*ans < summ:\n",
    "            return \"Bob\"\n",
    "        else:\n",
    "            return \"Tie\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        pre_sum = list(accumulate(stoneValue, initial = 0))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for j in range(1, 4):\n",
    "                res = max(res, pre_sum[-1] - pre_sum[i] - dfs(i + j))\n",
    "            return res\n",
    "        alice = dfs(0)\n",
    "        #print(alice)\n",
    "        if alice * 2 > pre_sum[-1]: return 'Alice'\n",
    "        if alice * 2 == pre_sum[-1]: return 'Tie'\n",
    "        return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:        \n",
    "        n = len(stoneValue)\n",
    "        sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            sum[i] = sum[i-1] + stoneValue[i]\n",
    "\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            nonlocal sum, n\n",
    "            if s == n:\n",
    "                return 0\n",
    "            ma = -float('inf')\n",
    "            for x in range(1, 4):\n",
    "                if s + x > n:\n",
    "                    break\n",
    "                ma = max(ma, sum[n - 1] - sum[s-1] - dfs(s + x))\n",
    "            print(s, ma)\n",
    "            return ma\n",
    "                \n",
    "        r = dfs(0)\n",
    "        if r * 2> sum[-2]:\n",
    "            return 'Alice'\n",
    "        elif r * 2 == sum[-2]:\n",
    "            return 'Tie'\n",
    "        else:\n",
    "            return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        total = sum(stoneValue)\n",
    "        memo = {}\n",
    "        n = len(stoneValue)\n",
    "        s = [0]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            s[i]=s[i+1]+ stoneValue[i]\n",
    "        def dp(i):\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            best = float('-inf')\n",
    "            for j in range(3):\n",
    "                if i+j<n:\n",
    "                    best = max(best,sum(stoneValue[i:i+j+1])+s[i+j+1]-dp(i+j+1) )\n",
    "            memo[i] = best\n",
    "            return best\n",
    "        ans = dp(0)\n",
    "        if ans*2>total:\n",
    "            return \"Alice\"\n",
    "        if ans*2==total:\n",
    "            return \"Tie\"\n",
    "        return \"Bob\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        sup = [0] * (n + 1)  # 后缀和\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            sup[i] = sup[i + 1] + stoneValue[i]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n: return 0\n",
    "            if i == n - 1: return stoneValue[i]\n",
    "            res = stoneValue[i] + (sup[i + 1] - dfs(i + 1))\n",
    "            if i < n - 1:\n",
    "                res = max(res, stoneValue[i] + stoneValue[i + 1] + (sup[i + 2] - dfs(i + 2)))\n",
    "            if i < n - 2:\n",
    "                res = max(res, stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + (sup[i + 3] - dfs(i + 3)))\n",
    "            return res\n",
    "        res = dfs(0)\n",
    "        if res * 2 > sup[0]:\n",
    "            return 'Alice'\n",
    "        elif res * 2 == sup[0]:\n",
    "            return 'Tie'\n",
    "        else:\n",
    "            return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: [int]) -> str:\n",
    "        piles=stoneValue\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ll: int, rr: int):\n",
    "            if ll>rr: return 0\n",
    "            if ll==rr: return piles[ll]\n",
    "            tmp=-sys.maxsize\n",
    "            if rr>=ll:\n",
    "                tmp1 = piles[ll] - dfs(ll + 1, rr)\n",
    "                tmp=max(tmp,tmp1)\n",
    "            if rr-ll>=1:\n",
    "                tmp2 = piles[ll]+piles[ll+1]-dfs(ll+2, rr)\n",
    "                tmp = max(tmp, tmp2)\n",
    "            if rr-ll>=2:\n",
    "                tmp3 = piles[ll]+piles[ll+1]+piles[ll+2]-dfs(ll+3, rr)\n",
    "                tmp = max(tmp, tmp3)\n",
    "            return tmp\n",
    "\n",
    "        ans=dfs(0, len(piles) - 1)\n",
    "        if ans>0: return \"Alice\"\n",
    "        elif ans<0: return \"Bob\"\n",
    "        else: return \"Tie\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        s = sum(stoneValue)\n",
    "        s1 = s\n",
    "        score = [s]\n",
    "        for i in range(len(stoneValue)):\n",
    "            s -= stoneValue[i]\n",
    "            score.append(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == len(stoneValue):\n",
    "                return 0\n",
    "            ans = -inf\n",
    "            for j in range(i,min(i+3,len(stoneValue))):\n",
    "                ans = max(ans,score[i]-dfs(j+1))\n",
    "            return ans\n",
    "\n",
    "        alice = dfs(0)\n",
    "        bob = s1 - alice\n",
    "        if alice > bob:\n",
    "            return 'Alice'\n",
    "        elif alice < bob:\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            return 'Tie'\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def advantage(i, j):\n",
    "            if i>j: return 0\n",
    "            res = float(\"-inf\")\n",
    "            for x in range(1,4):\n",
    "                # i+x最大可以取到j+1\n",
    "                if i+x>j+1: continue\n",
    "                # res = max(res, sum(stoneValue[i:i+x])-advantage(i+x, j))\n",
    "                # 使用前缀和\n",
    "                res = max(res, presum[i+x-1]-presum[i-1]-advantage(i+x, j))\n",
    "            return res\n",
    "\n",
    "        # presum[-1]是为0服务的\n",
    "        presum = [0]*(len(stoneValue)+1)\n",
    "        pres = 0\n",
    "        for i, x in enumerate(stoneValue):\n",
    "            pres+=x\n",
    "            presum[i] = pres\n",
    "\n",
    "        res = advantage(0, len(stoneValue)-1)\n",
    "        if res>0: return \"Alice\"\n",
    "        elif res==0: return \"Tie\"\n",
    "        else: return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "\n",
    "        pres = list(accumulate(stoneValue, initial=0))\n",
    "        n = len(stoneValue)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for k in range(1, 4):\n",
    "                if i + k <= n:\n",
    "                    res = max(res, pres[i + k] - pres[i] - dfs(i + k, j))\n",
    "            return res\n",
    "        res = dfs(0, n - 1)\n",
    "        return 'Alice' if res > 0 else 'Tie' if res == 0 else 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        @cache\n",
    "        def play(i):\n",
    "            if i == len(stoneValue):\n",
    "                return (0, 0)\n",
    "            \n",
    "            first = second = float('-inf')\n",
    "            for j in range(i, min(i + 3, len(stoneValue))):\n",
    "                next_first, next_second = play(j + 1)\n",
    "                if next_second + sum(stoneValue[i:j + 1]) > first:\n",
    "                    first = next_second + sum(stoneValue[i:j + 1])\n",
    "                    second = next_first\n",
    "            \n",
    "            return (first, second)\n",
    "\n",
    "        first, second = play(0)\n",
    "\n",
    "        if first > second:\n",
    "            return 'Alice'\n",
    "        elif first == second:\n",
    "            return 'Tie'\n",
    "        else:\n",
    "            return 'Bob'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        s = [stoneValue[-1]] * n\n",
    "        for i in range(n - 2, -1 , -1):\n",
    "            s[i] = s[i + 1] + stoneValue[i]\n",
    "\n",
    "        ans = [0] * (n+1)\n",
    "        X = [0] * n\n",
    "        # 回溯\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(st):\n",
    "            if st >= n:\n",
    "                return 0\n",
    "            \n",
    "            max_score = -float(\"inf\")\n",
    "            t = st\n",
    "            for x in range(1, 3 + 1):\n",
    "        #        max_score = max(max_score, s[st] - helper(st+x))\n",
    "                \n",
    "                if max_score < s[st] - helper(st+x):\n",
    "                    max_score = s[st] - helper(st+x)\n",
    "                    t = st + x\n",
    "\n",
    "            ans[st] = max_score\n",
    "            X[st] = t\n",
    "            return max_score\n",
    "\n",
    "        helper(0)\n",
    "\n",
    "        if ans[0] > ans[X[0]]:\n",
    "            return \"Alice\"\n",
    "        elif ans[0] == ans[X[0]]:\n",
    "            return \"Tie\"\n",
    "        else:\n",
    "            return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, s: List[int]) -> str:\n",
    "        n=len(s)\n",
    "        pre=[0]+list(accumulate(s))\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            if l>r:return 0\n",
    "            if r==l:\n",
    "                return s[l]\n",
    "            ans=-inf\n",
    "            for i in range(3):\n",
    "                if l+i<=r:\n",
    "                    ans=max(ans,pre[l+i+1]-pre[l]-dfs(l+i+1,r))\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        res= dfs(0,n-1)\n",
    "        return \"Alice\" if res>0 else (\"Bob\" if res<0 else \"Tie\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        \n",
    "        presum = [0]\n",
    "        for i in stoneValue:\n",
    "            presum.append(presum[-1]+i)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            ans = float(\"-inf\")\n",
    "            if i > j:\n",
    "                return 0\n",
    "            for k in range(3):\n",
    "                if i+k <= j:\n",
    "                    ans = max(ans, presum[j+1] - presum[i] - dp(i+k+1,j))\n",
    "            return ans\n",
    "        n = len(stoneValue)\n",
    "        ans = dp(0,n-1)\n",
    "        if presum[n] - ans < ans:\n",
    "            return \"Alice\"\n",
    "        elif  presum[n] - ans > ans:\n",
    "            return \"Bob\"\n",
    "        else:\n",
    "            return \"Tie\"\n",
    "        \n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        length = len(stoneValue)\n",
    "        memo = defaultdict()\n",
    "        sum_memo = defaultdict()\n",
    "        sum_memo[length - 1] = stoneValue[-1]\n",
    "        for i in range(length - 2, -1, -1):\n",
    "            sum_memo[i] = sum_memo[i + 1] + stoneValue[i]\n",
    "\n",
    "        def dfs(i):\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            if i == length - 1:\n",
    "                memo[i] = stoneValue[-1]\n",
    "                return stoneValue[-1]\n",
    "            if length <= i:\n",
    "                memo[i] = 0\n",
    "                return 0\n",
    "            for x in range(1, 4):\n",
    "                memo[i] = max(memo.get(i, float('-inf')), sum_memo[i] - dfs(i + x))\n",
    "            return memo[i]\n",
    "\n",
    "        dfs(0)\n",
    "        if sum(stoneValue) - memo[0] < memo[0]:\n",
    "            return \"Alice\"\n",
    "        elif sum(stoneValue) - memo[0] == memo[0]:\n",
    "            return \"Tie\"\n",
    "        else:\n",
    "            return \"Bob\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        # F[i] = S[i-1] - F[i-1], S[i-2] - F[i-2], S[i-3] - F[i-3]\n",
    "        nums = stoneValue[::-1]\n",
    "        S = []\n",
    "        s = 0\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            S.append(s)\n",
    "            \n",
    "        from functools import lru_cache\n",
    "        \n",
    "        @lru_cache(100000)\n",
    "        def foo(i):\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            elif i == 0:\n",
    "                return nums[0]\n",
    "            else:\n",
    "                inf = float('inf')\n",
    "                res = max(S[i]-foo(i-1), S[i]-foo(i-2) if i >= 1 else -inf, S[i]-foo(i-3) if i >= 2 else -inf)\n",
    "                # print(nums[:i+1], res, S[i])\n",
    "                return res \n",
    "        \n",
    "        r = foo(len(nums)-1)\n",
    "        o = S[-1] - r\n",
    "        \n",
    "        \n",
    "        if r == o:\n",
    "            return 'Tie'\n",
    "        elif r > o:\n",
    "            return 'Alice'\n",
    "        else:\n",
    "            return 'Bob'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "    \tn=len(stoneValue)\n",
    "    \tpre=[0]*(n+1)\n",
    "    \tfor i in range(n):\n",
    "    \t\tpre[i+1]=pre[i]+stoneValue[i]\n",
    "\n",
    "    \tinf=float('-inf')\n",
    "    \t# 在[l,r]范围获得的最大石子数\n",
    "    \t@functools.lru_cache(None)\n",
    "    \tdef f(l,r):\n",
    "    \t\tif l>r:return 0\n",
    "    \t\tif l==r:return stoneValue[l]\n",
    "    \t\ttotal=pre[r+1]-pre[l]\n",
    "\n",
    "    \t\tres=inf\n",
    "    \t\tfor i in range(l,l+3):\n",
    "    \t\t\t# total=(pre[i+1]-pre[l])+(pre[r+1]-pre[i+1])\n",
    "    \t\t\tres=max(res, total-f(i+1,r))\n",
    "    \t\treturn res\n",
    "\n",
    "    \tfst=f(0,n-1)\n",
    "    \tif fst>pre[n]-fst:return 'Alice'\n",
    "    \telif fst<pre[n]-fst:return 'Bob'\n",
    "    \telse:return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            stoneValue[i] += stoneValue[i+1]\n",
    "        self.stoneValue = stoneValue\n",
    "        # print(stoneValue)\n",
    "        alice = self.dfs(0)\n",
    "\n",
    "        # print(\"alice {}, bob {}\".format(alice, stoneValue[0] - alice))\n",
    "        if alice > stoneValue[0] - alice:\n",
    "            return \"Alice\"\n",
    "        elif alice < stoneValue[0] - alice:\n",
    "            return \"Bob\"\n",
    "        return \"Tie\"\n",
    "    \n",
    "    @cache\n",
    "    def dfs(self, start):\n",
    "        n = len(self.stoneValue)\n",
    "\n",
    "        if start >= n:\n",
    "            return 0\n",
    "        if start == n -1:\n",
    "            return self.stoneValue[start]\n",
    "        \n",
    "        return self.stoneValue[start] - min( self.dfs(i) for i in range(start+1, min(n+1,start+4)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools, sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue) -> str:\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(i):\n",
    "            if i >= len(stoneValue):\n",
    "                return 0\n",
    "            if i == len(stoneValue) - 1:\n",
    "                return stoneValue[-1]\n",
    "            ans = -sys.maxsize\n",
    "            total = _sum(i)\n",
    "            for x in range(3):\n",
    "                if i + x >= len(stoneValue): continue\n",
    "                ans = max(ans, total - helper(i + x + 1))\n",
    "            return ans\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def _sum(i):\n",
    "            if i >= len(stoneValue): return 0\n",
    "            return stoneValue[i] + _sum(i+1)\n",
    "        \n",
    "        A = helper(0)\n",
    "        B = sum(stoneValue) - A\n",
    "        if A == B: return 'Tie'\n",
    "        if A > B: return 'Alice'\n",
    "        else: return 'Bob'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        l = len(stoneValue)\n",
    "        prefix = [0] * (l + 1)\n",
    "        for n in range(l):\n",
    "            prefix[n+1] = prefix[n] + stoneValue[n]\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, first):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            if i == j - 1:\n",
    "                return stoneValue[i] if first else 0\n",
    "            max_val = float('-inf')\n",
    "            max_k = 0\n",
    "            for k in range(i + 1, min(i + 4, j + 1)):\n",
    "                curr = prefix[k] - prefix[i] + dp(k, j, False)\n",
    "                if curr > max_val:\n",
    "                    max_val = curr\n",
    "                    max_k = k\n",
    "            return max_val if first else dp(max_k, j, True)\n",
    "\n",
    "        first = dp(0, l, True)\n",
    "        second = dp(0, l, False)\n",
    "        if first > second:\n",
    "            return 'Alice'\n",
    "        elif first < second:\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = None\n",
    "        self.sv = None\n",
    "        self.total = None\n",
    "        self.dp = None\n",
    "\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        \"\"\"\n",
    "        :param stoneValue:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.total = sum(stoneValue)\n",
    "        dp = {}\n",
    "        cache = 0\n",
    "        for k, v in enumerate(stoneValue):\n",
    "            cache += v\n",
    "            dp[k] = cache\n",
    "        dp[-1] = 0\n",
    "        self.dp = dp\n",
    "\n",
    "        self.s = len(stoneValue)\n",
    "        self.sv = stoneValue\n",
    "        maxscore = self.getN(0, )\n",
    "        if self.total % 2 != 0:\n",
    "            if maxscore * 2 > self.total:\n",
    "                return 'Alice'\n",
    "            return 'Bob'\n",
    "        else:\n",
    "            if maxscore > self.total // 2:\n",
    "                return 'Alice'\n",
    "            if maxscore < self.total // 2:\n",
    "                return 'Bob'\n",
    "            return 'Tie'\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def getN(self, idx, ):\n",
    "        if idx == self.s:\n",
    "            return 0\n",
    "        if idx == self.s - 1:\n",
    "            return self.sv[idx]\n",
    "        if idx == self.s - 2:\n",
    "            if self.sv[idx] >= 0 and self.sv[idx + 1] >= 0:\n",
    "                return self.sv[idx] + self.sv[idx + 1]\n",
    "            if self.sv[idx] >= 0 >= self.sv[idx + 1]:\n",
    "                return self.sv[idx]\n",
    "            if self.sv[idx] < 0 < self.sv[idx + 1]:\n",
    "                return self.sv[idx] + self.sv[idx + 1]\n",
    "            if self.sv[idx] < 0 and self.sv[idx + 1] < 0:\n",
    "                return self.sv[idx]\n",
    "\n",
    "        maxV = -math.inf\n",
    "\n",
    "        for i in range(3):\n",
    "            idx1 = idx + i\n",
    "            if idx1 >= self.s:\n",
    "                break\n",
    "            sum1 = 0\n",
    "            for x in range(idx, idx + i + 1):\n",
    "                sum1 += self.sv[x]\n",
    "            val1 = sum1 + self.total - self.dp[idx1] - self.getN(idx1 + 1, )\n",
    "            maxV = max(maxV, val1)\n",
    "\n",
    "        return maxV\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "\n",
    "        sumstone = [0] * n\n",
    "        sumstone[-1] = stoneValue[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            sumstone[i] = stoneValue[i] + sumstone[i+1]\n",
    "        \n",
    "        @cache\n",
    "        def first(i):\n",
    "            if i >= n-3:\n",
    "                if i == n-1:\n",
    "                    return stoneValue[i]\n",
    "                elif i == n-2:\n",
    "                    return max(sum(stoneValue[-2:]),stoneValue[-2])\n",
    "                elif i == n-3:\n",
    "                    return max(sum(stoneValue[-3:]),stoneValue[-3]+stoneValue[-2],stoneValue[-3]+last(n-2))\n",
    "            \n",
    "            return max(stoneValue[i]+last(i+1),stoneValue[i]+stoneValue[i+1]+last(i+2),stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]+last(i+3))\n",
    "\n",
    "        @cache\n",
    "        def last(i):\n",
    "            return sumstone[i] - first(i)\n",
    "        \n",
    "        a = first(0)\n",
    "        b = last(0)\n",
    "\n",
    "        if a > b:\n",
    "            return 'Alice'\n",
    "        if a < b:\n",
    "            return 'Bob'\n",
    "        return 'Tie'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        inf = -(1 << 30)\n",
    "        dp = {}\n",
    "\n",
    "        def f(ab, x):\n",
    "            # max delta\n",
    "            if x >= len(stoneValue):\n",
    "                return 0\n",
    "            \n",
    "            if (ab, x) in dp:\n",
    "                return dp[(ab, x)]\n",
    "\n",
    "            v = 0\n",
    "            ans = inf\n",
    "            for i in range(3):\n",
    "                if (i+x) >= len(stoneValue):\n",
    "                    break\n",
    "\n",
    "                v += stoneValue[i+x]\n",
    "                res = f(1- ab, i+x+1)\n",
    "                ans = max(ans, v - res)\n",
    "        \n",
    "            dp[(ab,x)] = ans\n",
    "            return ans\n",
    "        \n",
    "        ans = f(0, 0)\n",
    "        # print(dp, ans)\n",
    "        if ans > 0:\n",
    "            ans = 'Alice'\n",
    "        elif ans < 0:\n",
    "            ans = 'Bob'\n",
    "        else:\n",
    "            ans = 'Tie'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIII(self, stoneValue: List[int]) -> str:\n",
    "        n = len(stoneValue)\n",
    "        @cache\n",
    "        def dp(isA, sI):#return the net score? #a want max(sA - sB), b want max(sB-sA)\n",
    "            sA, sB = 0, 0\n",
    "            if sI == n: return 0\n",
    "            ret = -inf\n",
    "            for ni in range(sI, min(sI+3, n)):\n",
    "                if isA: sA+=stoneValue[ni]\n",
    "                else: sB+= stoneValue[ni]\n",
    "                r = dp(not isA, ni+1)\n",
    "                if isA:\n",
    "                    ret = max(ret, (sA-r))\n",
    "                else:\n",
    "                    ret = max(ret, (sB-r))\n",
    "            return ret\n",
    "        r = dp(True, 0)\n",
    "        # print(r)\n",
    "        if r > 0: return 'Alice'\n",
    "        if r < 0: return 'Bob'\n",
    "        return 'Tie'\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
